package Leetcode第二期;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author : K k
 * @date : 9:52 2020/9/22
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 *
 *
 * 思路1：顺序合并（通过for循环一个一个链表进行合并）
 * 思路2：分治合并  递归二分合并
 * 思路3：使用优先队列合并  创建一个类实现Comparable,对所有链表进行排序。
 */
public class 合并K个升序链表_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeList(lists,0,lists.length-1);
    }

    //思路1：分治合并
    private ListNode mergeList(ListNode[] lists, int left, int right) {
        if(left==right){
            return lists[left];
        }
        if(left>right){
            return null;
        }
        int mid=(left+right)>>1;

        return merge(mergeList(lists,left,mid),mergeList(lists,mid+1,right));
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        if(l1==null || l2==null){
            return  l1==null? l2:l1;
        }
        ListNode head=new ListNode(0);
        ListNode node=head;
        ListNode a=l1,b=l2;
        while (a!=null && b!=null){
            if (a.val< b.val){
                node.next=a;
                a=a.next;
            }else {
                node.next=b;
                b=b.next;
            }
            node=node.next;
        }
        node.next= a==null?b:a;
        return head.next;
    }

}
